public class MyLinkedList implements ILinkedList{
    private ListNode head;
    public MyLinkedList(){
        head = null;
    }
    int size() {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }

    @Override
    public void display() {
        display(head);
    }
    static public void display(ListNode node) {
        ListNode cur = node;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
    }

    @Override
    public void addLast(int val) {
        if(head == null){
            head = new ListNode(val);
            return;
        }
        ListNode cur = head;
        while(cur.next != null) cur = cur.next;
        ListNode newNode = new ListNode(val);
        cur.next = newNode;
    }

    @Override
    public void addIndex(int index, int val) {
        int len = size();
        if(index < 0 || index > len) {
            System.out.println("index invalid");
            return;
        }
        if(index == 0) { addFirst(val); return; }
        if(index == len)  { addLast(val); return; }
        ListNode cur = head;
        for(int i = 0; i < index - 1; i++) cur = cur.next;
        ListNode newNode = new ListNode(val, cur.next);
        cur.next = newNode;
    }

    @Override
    public boolean contains(int val) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == val) return true;
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int index) {
        int len = size();
        if(index < 0 || index >= len){
            System.out.println("remove index invalid");
            return;
        }
        if(index == 0) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        for(int i = 0; i < index - 1; ++i) cur = cur.next;

        ListNode toDel = cur.next;
        cur.next = toDel.next;
    }

    // 头插法
    public ListNode reverse() {
        if(head == null) return null;
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }
    // 快慢
    public ListNode middleNode(){
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    static public ListNode merge(MyLinkedList list1, MyLinkedList list2, boolean distinct){
        // 不需要判空

        ListNode cur1 = list1.head;
        ListNode cur2 = list2.head;
        ListNode newHead = new ListNode(0,null);
        ListNode cur = newHead;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = new ListNode(cur1.val);
                cur1 = cur1.next;
                cur = cur.next;
            }
            else if(cur1.val > cur2.val){
                cur.next = new ListNode(cur2.val);
                cur2 = cur2.next;
                cur = cur.next;
            }
            else{
                cur.next = new ListNode(cur2.val);
                cur = cur.next;
                int val = cur1.val;
                if(distinct){
                    while(cur1 != null && cur1.val == val)cur1 = cur1.next;
                    while(cur2 != null && cur2.val == val)cur2 = cur2.next;
                }else{
                    cur1 = cur1.next;//只移动cur1，cur1.val变大了下一次就插cur2
                }
            }
        }
        while(cur1 != null){
            cur.next = new ListNode(cur1.val);
            cur1 = cur1.next;
            cur = cur.next;
        }
        while(cur2 != null){
            cur.next = new ListNode(cur2.val);
            cur2 = cur2.next;
            cur = cur.next;
        }
        return newHead.next;
    }
//    public ListNode mergelist(MyLinkedList other, boolean distinct){
//        return merge(this, other, distinct);
//    }
}
